import java.util.HashMap;

class Solution {
    public int[] topKFrequentBucket(int[] nums, int k) {
        List<Integer> res = new LinkedList<>();

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }

        List<Integer>[] list = new List[nums.length+1];
        for (int key : map.keySet()){
            int i = map.get(key);
            if (list[i] == null){
                list[i] = new ArrayList();
            }
            list[i].add(key);
        }

        for (int i = list.length-1; i >= 0 && res.size() < k; i--){
            if (list[i] == null) continue;
            res.addAll(list[i]);
        }
        int[] tmp = new int[k];

        return res.stream().mapToInt(Integer::valueOf).toArray();

    }
    
    public int[] topKFrequent(int[] nums, int k) {
        int[] heap = new int[k];
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0)+1);
        }

        int i = 0;
        for (int key : map.keySet()) {
            if (i < k){
                heap[i] = key;
            } else {
                if (i == k){
                    for (int j = k/2-1; j >= 0; j--) {
                        heapify(heap, j, k, map);
                    }
                }
                if (map.get(key) > map.get(heap[0])){
                    heap[0] = key;
                    heapify(heap, 0, k, map);
                }
            }
            i++;
        }
        return heap;
    }
    

    private void swap(int[] arr, int a, int b){
        int tmp = arr[a];
        arr[a] = arr[b];
        arr[b] = tmp;
    }

    private void heapify(int[] arr, int curr, int length, HashMap<Integer, Integer> map){
        int target = curr;
        int left = 2*curr+1;
        if (left < length && map.get(arr[left]) < map.get(arr[target])) {
            target = left;
        }

        int right = 2*curr+2;
        if (right < length && map.get(arr[right]) < map.get(arr[target])) {
            target = right;
        }

        if (target != curr){
            swap(arr, curr, target);
            heapify(arr, target, length, map);
        } 
    }
}